package thired.class15_kmp;

public class Class02_IsRotation {
    public static boolean isRotation(String a, String b) {
        if (a == null || b == null || a.length() != b.length()) {
            return false;
        }
        String b2 = b + b;
        return getIndexOf(b2, a) != -1;
    }

    private static int getIndexOf(String b2, String a) {
        char[] s1 = b2.toCharArray();
        char[] s2 = a.toCharArray();
        int[] nexts = getNexts(s2);
       int i = 0;
       int j = 0;
       while (i < s1.length && j < s2.length){
           if(s1[i] == s2[j]){
               i++;
               j++;
           }
           else if(nexts[j] != -1){
               j = nexts[j];
           }else{
               i++;
           }
       }
       return j == s2.length ? i - j : -1;
    }

    private static int[] getNexts(char[] s2) {
        int[] res = new int[s2.length];
        res[0] = -1;
        res[1] = 0;
        int i = 2;
        int cn = 0;
        while (i < res.length){
            if(s2[i - 1] == s2[cn]){
                res[i++] = ++cn;
            }
            if(cn > 0){
                cn = res[cn];
            }else{
                res[i++] = 0;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        String str1 = "yunzuocheng";
        String str2 = "zuochengyun";
        System.out.println(isRotation(str1, str2));

    }
}
